package leetcode.pre100;

import java.util.Arrays;

/**
 * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
 * <p>
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 给定一个只包含数字的非空字符串，请计算解码方法的总数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "12"
 * 输出: 2
 * 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
 * 示例 2:
 * <p>
 * 输入: "226"
 * 输出: 3
 * 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
 * <p>
 *
 * @since 2020/6/10 0010 下午 7:53
 */
public class Code91_DecodeNums_解码方法 {
    public static void main(String[] args) {
//        System.out.println(numDecodings("12"));
//        System.out.println(numDecodings("226"));
//        System.out.println(numDecodings("00"));
        System.out.println(numDecodings("101"));
    }

    public static int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;

        //方式1：暴力回溯
//        return process1(s, 0);
        //方式2：记忆性回溯
//        int[] memo = new int[s.length()];
//        Arrays.fill(memo, -1);
//        return process2(s, 0, memo);
        //方式3：dp
        return dp2(s);
    }

    /**
     * 从i开始，有多少种解码方法
     * <p>
     * 在当前位置为i下要注意几种特殊情况：
     * 1)如果当前位置为0，直接返回0，无法解码
     * 2)如果下一个位置为0，我们只能一次解码两个，如10,20
     * 但是要注意，大于20就不行了，如30,40
     *
     * @param s
     * @param i
     * @return
     */
    private static int process1(String s, int i) {
        if (i == s.length())
            return 1;
        //如果当前初始位置是0，直接返回0
        if (s.charAt(i) == '0') return 0;

        //如果是10,20则需要连续解码，但是如果单独解码1或者2，会进入递归基s.charAt(i) == 0 return 0

        //i位置解码,解码1个
        int m = process1(s, i + 1);
        int n = 0;
        if (i <= s.length() - 2) {
            //解码两个，要注意大于26不行
            int num = Integer.parseInt(s.substring(i, i + 2));
            if (num <= 26) {
                //i和i+1位置可以解码
                n = process1(s, i + 2);
            }
            //else 相当于>26,也就是上面算的m，解码一个
        }
        //返回当前位置为i时，解码的方法数
        return m + n;
    }

    /**
     * 方式2：记忆性回溯 2 2 6.....    2,2到6和22到6后面的答案是一样的，但是递归重复。
     * 也就是从i开始，解码数是固定的
     */
    private static int process2(String s, int i, int[] memo) {
        if (i == s.length())
            return 1;
        //如果当前初始位置是0，直接返回0
        if (s.charAt(i) == '0') return memo[i] = 0;

        if (memo[i] != -1) return memo[i];
        //如果是10,20则需要连续解码，但是如果单独解码1或者2，会进入递归基s.charAt(i) == 0 return 0

        //i位置解码,解码1个
        int m = process2(s, i + 1, memo);
        int n = 0;
        if (i <= s.length() - 2) {
            //解码两个，要注意大于26不行
            int num = Integer.parseInt(s.substring(i, i + 2));
            if (num <= 26) {
                //i和i+1位置可以解码
                n = process2(s, i + 2, memo);
            }
            //else 相当于>26,也就是上面算的m，解码一个
        }
        //返回当前位置为i时，解码的方法数
        return memo[i] = m + n;
    }

    /**
     * 方式3：dp
     * <p>
     * dp[i]表示从i开始的解码个数
     * dp[i] = dp[i+1] + dp[i+2] ，有条件限制的
     */
    private static int dp(String s) {
        int len = s.length();
        //为了让 dp[len-2] 也可以写成统一处理
        int[] dp = new int[len + 1];
        //TODO 假设虚拟出的可以解码
        //如.....12  当i来到1这个位置，那么dp[i] = dp[i+1] + dp[len] ,
        // 此时dp[len] = 1表示连续解码12 这是一种策略
        dp[len] = 1;

        //只要有位数是0，当前位置dp就是0
        dp[len - 1] = s.charAt(len - 1) == '0' ? 0 : 1;
        for (int i = len - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') continue;  // default dp[i] = 0
            //如果当前位置 + 下一个位置 <= 26，可以一次解码1个或2个，否则只能解码一个，如27
            if (Integer.parseInt(s.substring(i, i + 2)) <= 26) {
                dp[i] = dp[i + 1] + dp[i + 2];
            } else {
                //只能解码i，然后到i+1
                dp[i] = dp[i + 1];
            }
        }
        return dp[0];
    }

    /**
     * 空间压缩
     */
    private static int dp2(String s) {
        int len = s.length();
        //TODO 假设虚拟出的可以解码
        //如.....12  当i来到1这个位置，那么dp[i] = dp[i+1] + dp[len] ,
        // 此时dp[len] = 1表示连续解码12 这是一种策略
        int pre2 = 1;
        int pre1 = s.charAt(len - 1) == '0' ? 0 : 1;
        int cur = pre1;
        for (int i = len - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                //更新当前
                cur = 0;
                //更新两个旧值
                pre2 = pre1;
                pre1 = cur;
                continue;  // default dp[i] = 0
            }
            //如果当前位置 + 下一个位置 <= 26，可以一次解码1个或2个，否则只能解码一个，如27
            if (Integer.parseInt(s.substring(i, i + 2)) <= 26) {
                //如s = 12，当前位置是1，那么解码1后就取决于2的解码。 解码12后，来到len处，该处是1
                cur = pre1 + pre2;
            } else {
                //只能解码i，然后到i+1
                cur = pre1;
            }
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;
    }
}
